An item may be stored as a row in a database. The item may be related to, at most, one other item, such as a “previous” or “parent” item, identified by information in one of the columns in the item's row. The item's “ancestry” may comprise, for example, the set of items that would be visited by starting from the item and then following the relationships until reaching another item with no such relationship (i.e. a root item of the hierarchy.)
For example, the item may comprise a web site (e.g. collections of web pages.) A designer who designed the pages contained in the web site may wish to display a set of links (i.e. a “breadcrumb”) to a set of web sites higher in the overall hierarchy of related web sites. The set of web sites so related to a particular web site may be referred to as the particular web site's “ancestry.”
One conventional process to determine an ancestry of an item is to query for each successive parent until reaching a root item. This approach requires one query for each ancestor item. If the number of ancestors for the item is known beforehand, another conventional process to determine the ancestry is to issue a single query making use of multiple table self-joins. There will be one join in the query for each ancestor item. Both of these conventional processes require more work as the depth of an item's ancestry grows. Using the example of a page in a web site, following either conventional processes for each request for the page would not be suitable for a high performance application, especially one with arbitrarily deep item hierarchies. Constructing the query that relies on self-joins may also be difficult because an algorithm may decide on some maximum number of ancestors that may be returned. That is, the query structure (e.g. in terms of the number of self-joins it performs) may be fixed, which may determine how many ancestors may be returned.